package tree.对称二叉树;

//给定一个二叉树，检查它是否是镜像对称的。
//
//
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
//
//
//
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
//
//
//
//
//
// 进阶：
//
// 你可以运用递归和迭代两种方法解决这个问题吗？
// Related Topics 树 深度优先搜索 广度优先搜索
// 👍 1261 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import sun.reflect.generics.tree.Tree;

/**
 * Definition for doubleDimensionalArrayPrint binary tree node.
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * @param root
     * @return boolean
     * 先判断根节点，为null返回true，为false则判断左节点和右节点，如果左节点和右节点不为空且相等则递归判断
     * 左节点的右节点==右节点的左节点
     * 左节点的左节点==右节点的右节点
     */
    public boolean isSymmetric(TreeNode root) {
        if (null == root) {
            return true;
        }
        TreeNode currentLeft = root.left;
        TreeNode currentRight = root.right;
        Boolean symmetric = isSymmetric(currentLeft, currentRight);
        return symmetric;
    }

    private Boolean isSymmetric(TreeNode tn1, TreeNode tn2) {
        if (tn1 == null) {
            return tn2 == null;
        }
        if (tn2 == null) {
            return tn1 == null;
        }
        Boolean left = isSymmetric(tn1.left, tn2.right);
        Boolean right = isSymmetric(tn1.right, tn2.left);
        return left & right & tn1.val == tn2.val;
    }


}
//leetcode submit region end(Prohibit modification and deletion)


